/*
 * @lc app=leetcode.cn id=746 lang=javascript
 *
 * [746] 使用最小花费爬楼梯
 */

// @lc code=start
/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function (cost) {
    let db=[0,0]//到底位置0，1均花费0
    let i=2//从到底第三个位置开始算
    for(;i<=cost.length;i++){
        db[i]=Math.min(db[i-1]+cost[i-1],db[i-2]+cost[i-2])//两种到达方式，一种从前一个位置，一种前两个位置处，到达点为cost数组最末还有后面，比如例子1到达是20后面一个数，输出的是DB（3）,开始选位置1,或者位置2，位置2，
    }
    console.log(db)
    return db[i-1]
};
// @lc code=end

var minCostClimbingStairs = function (cost) {
    let map = new Map()
    let dfs = function (cost) {
        if (cost.length == 0) return 0
        if (cost.length == 1) return cost[0]
        if (map.has(cost)) return map.get(cost.length)
        else {
            map.set(cost.length, Math.min(cost[1] + dfs(cost.slice(2)), cost[0] + dfs(cost.slice(1))))
        }
        return map.get(cost.length)
    }
    cost.push(0)
    return dfs(cost)
};//递归应该可以但是超时了，应该采用动态规划。